# Python 2.6.4
# Project Euler, Problem 72
# Copyright 2010 Talha Zaman

def factors(limit):
    sieve = [[] for i in range(0, limit)]
    sieve[0] = sieve[1] = [1]
    for i in range(2,limit):
        if len(sieve[i]): continue
        for j in range(2*i, limit, i):
            sieve[j].append(i)
    return sieve

def phi(n, fac):
    if len(fac[n])==0: return n-1
    for f in fac[n]: n = n*(f-1) / f
    return n

fac = factors(1000001)
print sum(phi(i, fac) for i in range(2,1000001))
